package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 剑指offer
 * 按之字形顺序打印二叉树
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：395311
 * 本题知识点： 栈 树
 * 算法知识视频讲解
 * 题目描述
 * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
 * 示例1
 * 输入
 * 复制
 * {8,6,10,5,7,9,11}
 * 返回值
 * 复制
 * [[8],[10,6],[5,7,9,11]]
 */
public class ZhiPrintBinaryTree {

    @Test
    public void testPrint(){
        TreeNode root = new TreeNode(8);

        TreeNode treeNode = root;

        treeNode.left = new TreeNode(4);
        treeNode.right = new TreeNode(12);
        treeNode.left.left = new TreeNode(2);
        treeNode.left.right = new TreeNode(6);
        treeNode.right.left = new TreeNode(10);
        treeNode.right.right = new TreeNode(14);
        treeNode.left.left.left = new TreeNode(1);
        treeNode.left.left.right = new TreeNode(3);
        treeNode.left.right.left = new TreeNode(5);
        treeNode.left.right.right = new TreeNode(7);
        treeNode.right.left.left = new TreeNode(9);
        treeNode.right.left.right = new TreeNode(11);
        treeNode.right.right.left = new TreeNode(13);
        treeNode.right.right.right = new TreeNode(15);

        ArrayList<ArrayList<Integer>> print = Print(root);
        System.out.println(print);
    }

//    利用栈的特性，然后递归（注意需要导入栈的依赖）
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer>> printResult = new ArrayList<>();

        if (pRoot == null) {
            return printResult;
        }

        //碰到逆序的时候要想到栈！！！
        Stack<TreeNode> floorNode = new Stack<>();
        floorNode.push(pRoot);

        Print(1, printResult,floorNode);

        return printResult;
    }

    private void Print(int floor, ArrayList<ArrayList<Integer>> printResult, Stack<TreeNode> floorNode) {

        if (floorNode.size() == 0) {
            return;
        }

        //将上一层存进结果中
        ArrayList<Integer> temp = new ArrayList<>();
        for (TreeNode treeNode : floorNode) {
            temp.add(treeNode.val);
        }
        printResult.add(temp);

        Stack<TreeNode> nextFloorNode = new Stack<>();

        while (!floorNode.empty()){
            TreeNode node = floorNode.pop();
            if (floor % 2 == 0) {
                if (node.left!=null) {
                    nextFloorNode.push(node.left);
                }
                if (node.right!=null) {
                    nextFloorNode.push(node.right);
                }
            } else {
                if (node.right!=null) {
                    nextFloorNode.push(node.right);
                }
                if (node.left!=null) {
                    nextFloorNode.push(node.left);
                }
            }
        }

        Print(floor + 1, printResult, nextFloorNode);
    }
}
